Design Automation is Hard.
Deal with It.
(or: Bad News About Filter Minimization)

 

Jason O'Kane

University of South Carolina

Computer Science and Engineering

Collaborators

 


Dylan
Shell

Fatemeh
Saberifar

Shervin
Ghasemlou

Jeremy
Lewis

Claim 1

There is no need to build good robots.

 

Instead: The really interesting problems are in overcoming the limitations of minimal hardware, using the power of algorithms.

Navigation with a Roomba-like Robot

[ijrr 2012]

Automated design?

The classic algorithm for minimal design looks like this:
  1. Think of a problem. Call it $x$.
  2. Hire a good graduate student to work on $x$.
  3. Wait at least a few months.
  4. Success!

Minimal Combinatorial Filters

[Tovar, Cohen, Bobadilla, Czarnowsi, and LaValle, 2014]
. . . Can we automate this process?

Claim 2

Algorithms for general-purpose robot design problems would be great. . .

. . . but all of the interesting questions are NP-hard.

Filter Reduction

[icra 2013]
Given a filter expressed as a transition graph:
  • Edges are labeled with observations.
  • Vertices ("states") are labeled with outputs that define a task.

 

We want to find:
  • the smallest filter that produces
  • the same output for
  • all plausible observation strings.

Example

 

Bad News

Theorem The problem of optimal reduction of combinatorial filters is NP-hard.

Aside: Waiting for better computers won't help much.

Reminder from analysis of algorithms:

For an algorithm that runs in $O(2^n)$ time, holding time fixed and increasing computer speed from $x$ to $2x$, we increase the size of problems we can solve from $n$ to $n+1$.

Bad News

Theorem The problem of optimal reduction of combinatorial filters is NP-hard.
Corollary . . . even if the filter is a tree.
Corollary . . . even if approximation is enough.
Corollary . . . even if some mistakes are OK.
Corollary . . . even if parameters are fixed.

How Can We Deal with This Bad News?

We dream about this:
$\longrightarrow$
specification
$\longrightarrow$
design

But we should also be thinking about an iterative model:
questions
$\longleftarrow$
$\longrightarrow$
answers
$\longrightarrow$
design

Shameless Advertisement: Set-labeled filters and sensor transformations

[rss 2016]

Acknowledgements

More information:
http://cse.sc.edu/~jokane

 

Generous support from: